package pl.poznan.put.cs.to.tsp.localsearch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import pl.poznan.put.cs.to.tsp.common.Vertexes;

public class VertexTravelHandler implements IMoveHandler {
	private List<Integer> a;
	private List<Integer> b;
	private boolean left;
	private int first;
	private boolean improved;
	private Vertexes vertexes;
	private Random r;
	private TabuManager tabuManager;

	private int bestTabuV;
	private int bestTabuDelta;
	private int bestTabuActualPrev;
	private int bestTabuNewPrev;
	private int actual;
	private int actualPrev;
	private int actualNewPrev;
	private int actualDelta;

	public VertexTravelHandler(List<Integer> a, List<Integer> b,
			Vertexes vertexes, TabuManager tabuManager) {
		this.a = a;
		this.b = b;
		this.vertexes = vertexes;
		this.tabuManager = tabuManager;
		this.r = new Random();

		// System.out.println(">BEFORE<");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);

		this.improved = this.tryVertexTravel();

		// System.out.println(">AFTER<");
		// System.out.println("A:");
		// this.printList(this.a);
		// System.out.println("B:");
		// this.printList(this.b);
	}

	private boolean tryVertexTravel() {
		int startV = this.r.nextInt(this.vertexes.getNumberOfNodes());
		this.left = this.r.nextBoolean();

		this.bestTabuV = -1;
		this.bestTabuDelta = Integer.MAX_VALUE;
		this.bestTabuActualPrev = -1;
		this.bestTabuNewPrev = -1;

		this.actual = startV;
		List<Integer> list;

		do {
			if (this.inA(actual)) {
				list = this.a;
			} else {
				list = this.b;
			}

			int actualPos = list.indexOf(Integer.valueOf(actual));
			if (actualPos == -1) {
				throw new RuntimeException(
						"[VERTEX_TRAVEL ERROR] Trying to get position of vertex which doesn't exist in list");
			}

			this.actualPrev = list.get((actualPos - 1 + list.size())
					% list.size());

			this.actualNewPrev = this.findBestPrevForVertex(actual, list);

			if (this.actualDelta < 0) {
				if (this.tabuManager.isTabuVertex(Integer.valueOf(this.actual))) {
					if (this.bestTabuV == -1) {
						this.bestTabuV = this.actual;
						this.bestTabuDelta = this.actualDelta;
						this.bestTabuNewPrev = this.actualNewPrev;
						this.bestTabuActualPrev = this.actualPrev;
					} else {
						if (this.actualDelta < this.bestTabuDelta) {
							this.bestTabuV = this.actual;
							this.bestTabuDelta = this.actualDelta;
							this.bestTabuNewPrev = this.actualNewPrev;
						}
					}
				} else {
					// System.out.println("Preforming move! [not tabu!]");
					// this.printList(list);
					// System.out.println("v->" + this.actual + ", prev->"
					// + this.actualPrev + ", newprev->"
					// + this.actualNewPrev + ", delta->"
					// + this.actualDelta);
					this.performMove(list, this.actual, this.actualPrev,
							this.actualNewPrev, this.actualDelta);
					return true;
				}
			}

			if (this.left) {
				actual = (actual - 1 + this.vertexes.getNumberOfNodes())
						% this.vertexes.getNumberOfNodes();
			} else {
				actual = (actual + 1) % this.vertexes.getNumberOfNodes();
			}
		} while (actual != startV);

		if (this.bestTabuV != -1) {
			if (this.inA(this.bestTabuV)) {
				list = this.a;
			} else {
				list = this.b;
			}
			this.performMove(list, this.bestTabuV, this.bestTabuActualPrev,
					this.bestTabuNewPrev, this.bestTabuDelta);
			return true;
		}

		return false;
	}

	private void performMove(List<Integer> list, int v, int actualPrev,
			int newPrev, int delta) {
		list.remove(list.indexOf(Integer.valueOf(v)));
		list.add((list.indexOf(Integer.valueOf(newPrev)) + 1) % list.size(), v);
	}

	private int findBestPrevForVertex(int v, List<Integer> list) {
		int prev = -1;
		this.actualDelta = Integer.MAX_VALUE;

		List<Integer> cloned = new ArrayList<Integer>(list);
		cloned.remove(list.indexOf(Integer.valueOf(v)));

		for (int i : cloned) {
			int d = this.calculateInsertingDelta(cloned, i, v)
					+ this.calculateDeletingDelta(list, v);
			if (d < this.actualDelta) {
				prev = i;
				this.actualDelta = d;
			}
		}

		return prev;
	}

	private int calculateInsertingDelta(List<Integer> list, int prev, int v) {
		int succ = list.get((list.indexOf(Integer.valueOf(prev)) + 1)
				% list.size());
		int prevSucc = this.vertexes.getDistanceBetween(prev, succ);
		int prevV = this.vertexes.getDistanceBetween(prev, v);
		int succV = this.vertexes.getDistanceBetween(succ, v);

		return (prevV + succV - prevSucc);
	}

	private int calculateDeletingDelta(List<Integer> list, int v) {
		int vIndex = list.indexOf(Integer.valueOf(v));
		int prev = list.get((vIndex - 1 + list.size()) % list.size());
		int succ = list.get((vIndex + 1) % list.size());

		int prevSucc = this.vertexes.getDistanceBetween(prev, succ);
		int prevV = this.vertexes.getDistanceBetween(prev, v);
		int succV = this.vertexes.getDistanceBetween(succ, v);

		return (prevSucc - prevV - succV);
	}

	private boolean inA(int v) {
		return this.a.contains(Integer.valueOf(v));
	}

	// private void printList(List<Integer> list) {
	// for (int i : list) {
	// // System.out.print(i + " ");
	// }
	// // System.out.println();
	// // System.out.println("n = " + list.size());
	// }

	@Override
	public List<Integer> getA() {
		return this.a;
	}

	@Override
	public List<Integer> getB() {
		return this.b;
	}

	@Override
	public boolean hasImproved() {
		return this.improved;
	}
}
